package _go

import "sort"

//执行时间和内存 	40 ms	7.3 MB	Go
func threeSum(nums []int) [][]int {
	var res [][]int
	sort.Ints(nums)
	if len(nums)<3 {return [][]int{}}
	for i:=0 ; i<len(nums);i++{
		if nums[i] > 0 { return res}//排序后如果i大于0  后边的就不可能在有不重复的解了

		if( i>0&&nums[i] == nums[i-1]) {
			continue
		}
		l:= i+1
		r:= len(nums)-1
		for l<r {
			if( nums[i] + nums[l] + nums[r] == 0){
				res = append(res,[]int{ nums[i] , nums[l], nums[r]})
				//重复的数字直接跳过
				for l<r && nums[r] == nums[r-1]{
					r--
				}
				//重复的数字直接跳过
				for l<r && nums[l] == nums[l+1]{
					l++
				}
				l++
				r--
			}else if( nums[i] + nums[l]+nums[r] > 0){
				//数大了  r向左移动
				r--
			}else if( nums[i] + nums[l]+nums[r] < 0){
				//数小了  l向右移动
				l++
			}
		}
	}
	return res
}
